package LK_Algorithm;

public class Alg_Day_10 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead;
        ListNode tmp;
        if (list1 ==null){
            return list2;
        }
        if (list2 == null){
            return  list1;
        }
        if (list1.val <= list2.val){
            newHead=list1;
            tmp=list1;
            list1= list1.next;
        }else{
            newHead=list2;
            tmp=list2;
            list2= list2.next;
        }

        while (list1 !=null && list2 !=null){
            if (list1.val <= list2.val){
                tmp.next=list1;
                list1= list1.next;
                tmp=tmp.next;

            }else{
                tmp.next=list2;
                list2= list2.next;
                tmp=tmp.next;
            }
        }
        if (list1 !=null){
            tmp.next=list1;
        }
        if (list2 !=null){
            tmp.next=list2;
        }
        return newHead;

    }
    public ListNode reverseList(ListNode head) {
        //如果头结点为空返回空
        if (head==null)return null;

        ListNode cur=head.next;
        head.next=null;
        while (cur!=null){
            ListNode tmp=cur.next;
            cur.next=head;
            head=cur;
            cur=tmp;
        }
        return head;
    }
}
